import java.util.Arrays;
import java.util.HashMap;

/**
 * @author hewei
 * @version 1.0
 * @description: 1053. 交换一次的先前排列
 * @date 2022/10/24 14:54
 */

public class PrevPermOpt1 {

    public static void main(String[] args) {
        int[] nums = {1,9,4,6,7};
        System.out.println(Arrays.toString(new PrevPermOpt1().prevPermOpt1(nums)));
    }

    public int[] prevPermOpt1(int[] arr) {
        int min = Integer.MAX_VALUE;
        HashMap<Integer, Integer> map1 = new HashMap<>();
        HashMap<Integer, Integer> map2 = new HashMap<>();
        for (int i = arr.length - 1; i >= 0; i--) {
            if (!map1.containsKey(arr[i])) map1.put(arr[i], i);
            map2.put(arr[i], i);
            if (arr[i] <= min) {
                min = arr[i];
            } else {
                Integer index = map1.get(min);
                while (index < arr.length - 1 && arr[index + 1] < arr[i]) index = map1.get(arr[index + 1]);
                index = map2.get(arr[index]);
                int temp = arr[index];
                arr[index] = arr[i];
                arr[i] = temp;
                return arr;
            }
        }
        return arr;
    }
}
